﻿#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>

using namespace std;

#define INVALID_VALUE 0x1fffffff

typedef struct
{
	int timeCost;
	int profit;
}Activity;

typedef struct
{
	int timeCost;
	int profit;
}ActivityRecurReturnData;

static bool sortActivityRecurReturnDataFunc(const ActivityRecurReturnData& a, const ActivityRecurReturnData& b)
{
	if (a.profit == b.profit)
	{
		return a.timeCost < b.timeCost;
	}

	return b.profit < a.profit;
}

static ActivityRecurReturnData recur(const Activity* activities, size_t activityCount, unordered_map<int, vector<int>>& nextIndexes, int timeRemain, int index)
{
	ActivityRecurReturnData data;
	memset(&data, 0, sizeof(ActivityRecurReturnData));
	Activity cur = activities[index];

	if (timeRemain < cur.timeCost)
	{
		data.timeCost = INVALID_VALUE;
		return data;
	}

	auto nexts = nextIndexes[index];
	if (nexts.empty())
	{
		data.profit = cur.profit;
		data.timeCost = cur.timeCost;
	}
	else
	{
		vector<ActivityRecurReturnData> vec;
		for (auto it = nexts.begin(); it != nexts.end(); it++)
		{
			auto d = recur(activities, activityCount, nextIndexes, timeRemain - cur.timeCost, *it);
			if (d.timeCost < INVALID_VALUE)
			{
				vec.push_back(d);
			}
		}

		if (vec.empty())
		{
			data.timeCost = INVALID_VALUE;
		}
		else
		{
			sort(vec.begin(), vec.end(), sortActivityRecurReturnDataFunc);
			auto first = vec.begin();
			data.profit = cur.profit + first->profit;
			data.timeCost = cur.timeCost + first->timeCost;
		}
	}

	return data;
}

static void printMaxProfit(const Activity* activities, size_t activityCount, int totalTime, unordered_map<int, vector<int>>& nextIndexes)
{
	int maxProfit = 0;
	int timeCostWhenMaxProfit = 0;
	for (int i = 0; i < activityCount; i++)
	{
		auto d = recur(activities, activityCount, nextIndexes, totalTime, i);
		if (d.timeCost <= totalTime)
		{
			if (d.profit > maxProfit)
			{
				maxProfit = d.profit;
				timeCostWhenMaxProfit = d.timeCost;
			}
		}
	}
}

// CC直播的运营部门组织了很多运营活动，每个活动需要花费一定的时间参与，主播每参加完一个活动即可得到一定的奖励，
// 参与活动可以从任意活动开始，但一旦开始，就需要将后续活动参加完毕(注意：最后一个活动必须参与), 活动之间存在一定的
// 依赖关系(不存在环的情况)，现在给出所有的活动时间与依赖关系，以及给出有限的时间，请帮主播计算在有限的时间内，
// 能获得的最大奖励，以及需要的最少时长。
//
// 输入描述：
// 第一行输入数据N与D，表示有N项活动，D表示给予的时长，0 < N <= 1000, 0 < D <= 10000.
//	从第二行开始到N + 1行，每行描述一个活动的信息，其中第一项表示当前活动需要花费的时间t，第二项表示可以获得的奖励a，之后
//	有N项数据，表示当前活动与其他活动的依赖关系，1表示有依赖，0表示无依赖，每项数据用空格分开
//	
//	输出描述：
//	输出两项数据A与T，用空格分割，A表示所获得的最大奖励，T表示所需要的时长。
//	
//	输入:
// 8 10
// 3 2000 0 1 1 0 0 0 0 0
// 3 4000 0 0 0 1 1 0 0 0
// 2 2500 0 0 0 1 0 0 0 0
// 1 1600 0 0 0 0 1 1 1 0
// 4 3800 0 0 0 0 0 0 0 1
// 2 2600 0 0 0 0 0 0 0 1
// 4 4000 0 0 0 0 0 0 0 1
// 3 3500 0 0 0 0 0 0 0 0
//
// 输出
// 11700 9
//
//       B       E
//     ↗  \     ↗ \
//   /      ↘ /     ↘
//  A        D--->G--> H
//   \    ↗  \     ↗
//    ↘ /     ↘ /
//     C        F
//
//活动 | 所需时间(天) | 获得的奖励(C币)
// A       3             2000
// B       3             4000
// C       2             2500
// D       1             1600
// E       4             3800
// F       2             2600
// G       4             4000
// H       3             3500
//
//如上图数据所示，给定有限时间为10天，可以取得最大奖励为:11700, 需要的时长：9天，参加的活动为BDFH四个
//
// 思路 :
//	使用有序表，将各条路线的总天数与总时长整理在一起，使用天数作为主键，然后看天数与收益的递增趋势，如果有记录违反了天数↑ - 收益↑的，将它拿掉，
//	 然后取收益最大的那条记录。
int main_MaxProfitWithFewerDays()
{
	char input[][256] = {
		"8 10",
		"3 2000 0 1 1 0 0 0 0 0",
		"3 4000 0 0 0 1 1 0 0 0",
		"2 2500 0 0 0 1 0 0 0 0",
		"1 1600 0 0 0 0 1 1 1 0",
		"4 3800 0 0 0 0 0 0 0 1",
		"2 2600 0 0 0 0 0 0 0 1",
		"4 4000 0 0 0 0 0 0 0 1",
		"3 3500 0 0 0 0 0 0 0 0",
	};

	int activityCount = 0;
	int totalTime = 0;
	sscanf_s(input[0], "%d %d", &activityCount, &totalTime);
	Activity* activities = (Activity*)malloc(sizeof(Activity) * activityCount);
	memset(activities, 0, sizeof(Activity) * activityCount);
	unordered_map<int, vector<int>> activityNexts;

	for (int i = 0; i < activityCount; i++)
	{
		Activity act;
		vector<int> actIndexes;
		char* cur = input[i + 1];
		int index = 0;
		size_t len = strlen(cur);
		int numberIndex = 0;
		int lastSpaceIndex = -1;
		char tmp[100];
		memset(tmp, 0, sizeof(tmp));
		while (index < len)
		{
			char c = cur[index];
			if (c == ' ')
			{
				memset(tmp, 0, sizeof(tmp));
				memcpy(tmp, cur + lastSpaceIndex + 1, index - lastSpaceIndex);
				if (numberIndex == 0)
				{
					sscanf_s(tmp, "%d", &act.timeCost);
				}
				else if (numberIndex == 1)
				{
					sscanf_s(tmp, "%d", &act.profit);
					memcpy(activities + i, &act, sizeof(Activity));
				}
				else
				{
					int nextActIndex = 0;
					sscanf_s(tmp, "%d", &nextActIndex);
					if (nextActIndex > 0)
					{
						actIndexes.push_back(numberIndex - 2);
					}
				}

				++numberIndex;
				lastSpaceIndex = index;
			}

			++index;
		}

		memset(tmp, 0, sizeof(tmp));
		memcpy(tmp, cur + lastSpaceIndex + 1, index - lastSpaceIndex);
		int nextActIndex = 0;
		sscanf_s(tmp, "%d", &nextActIndex);
		if (nextActIndex > 0)
		{
			actIndexes.push_back(numberIndex - 2);
		}

		activityNexts[i] = actIndexes;
	}

	printMaxProfit(activities, activityCount, totalTime, activityNexts);
	free(activities);
	return 0;
}